home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / incl / LEDA.020+881 / d_array.h < prev    next >
C/C++ Source or Header  |  1994-08-05  |  5KB  |  159 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  d_array.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_D_ARRAY_H
  17. #define LEDA_D_ARRAY_H
  18.  
  19. //------------------------------------------------------------------------------
  20. // d_array 
  21. //------------------------------------------------------------------------------ 
  22. #include <LEDA/impl/skiplist.h> 
  23. #define DA_DEF_IMPL skiplist
  24. typedef skiplist_item d_array_item;
  25.  
  26.  
  27. template<class itype, class etype> 
  28.  
  29. class _CLASSTYPE d_array : public virtual DA_DEF_IMPL 
  30. {
  31.  
  32. etype init;
  33. d_array_item iterator;
  34.  
  35. int  cmp(GenPtr x, GenPtr y) const
  36.                           { return compare(ACCESS(itype,x),ACCESS(itype,y)); }
  37. void clear_key(GenPtr& x)   const { Clear(ACCESS(itype,x)); }
  38. void clear_inf(GenPtr& x)   const { Clear(ACCESS(etype,x)); }
  39. void copy_key(GenPtr& x)    const { x=Copy(ACCESS(itype,x));  }
  40. void copy_inf(GenPtr& x)    const { x=Copy(ACCESS(etype,x));  }
  41. int  int_type()             const { return INT_TYPE(itype); }
  42.  
  43. public:
  44.  
  45. virtual etype&  operator[](itype y) 
  46. { d_array_item i=DA_DEF_IMPL::lookup(Convert(y));
  47.   if (i==nil) i=DA_DEF_IMPL::insert(Convert(y),Convert(init));
  48.   return ACCESS(etype,info(i)); 
  49. }
  50.  
  51. virtual bool defined(itype y)  const 
  52. { return (DA_DEF_IMPL::lookup(Convert(y))!=nil); }
  53.  
  54. virtual void start_iteration() const 
  55. { (d_array_item&)iterator = DA_DEF_IMPL::first_item(); }
  56.  
  57. virtual bool next_index(itype& y) const    
  58. { if (iterator==0) return false;
  59.   else { y = ACCESS(itype,key(iterator));
  60.          (d_array_item&)iterator = DA_DEF_IMPL::next_item(iterator);
  61.          return true; 
  62.         } 
  63. }
  64.  
  65. d_array<itype,etype>& operator=(const d_array<itype,etype>& A)
  66. { DA_DEF_IMPL::operator=(A); init=A.init; return *this; }
  67.  
  68.  
  69. d_array()        { Init(init); }
  70. d_array(etype i) { init=i; }
  71.  
  72. d_array(const d_array<itype,etype>& A) : DA_DEF_IMPL(A) {init=A.init;}
  73.  
  74. virtual ~d_array() { clear(); }
  75.  
  76. };
  77.  
  78. #define forall_defined(i,A)  for ((A).start_iteration(); (A).next_index(i); )
  79.  
  80.  
  81.  
  82. //------------------------------------------------------------------------------
  83. //
  84. // Dictionary arrays with implementation parameter:
  85. //
  86. //   _d_array<itype,etype,impl> 
  87. //
  88. //------------------------------------------------------------------------------
  89.  
  90.  
  91. #define _d_array_class(itype,etype,impl)\
  92. \
  93. class _CLASSTYPE _d_array_class_(itype,etype,impl):private virtual impl,\
  94.                                                    public d_array<itype,etype>\
  95. {\
  96. \
  97. etype init; /* because of a bug in g++ I use "this->init" for accessing it*/\
  98. d_array_item iterator;\
  99. \
  100. int cmp(GenPtr x, GenPtr y) const\
  101. { return compare(ACCESS(itype,x),ACCESS(itype,y)); }\
  102. void clear_key(GenPtr& x) const { Clear(ACCESS(itype,x)); }\
  103. void clear_inf(GenPtr& x) const { Clear(ACCESS(etype,x)); }\
  104. void copy_key(GenPtr& x) const { x=Copy(ACCESS(itype,x)); }\
  105. void copy_inf(GenPtr& x) const { x=Copy(ACCESS(etype,x)); }\
  106. void print_key(GenPtr x) const { Print(ACCESS(itype,x),cout); }\
  107. void print_inf(GenPtr x) const { Print(ACCESS(etype,x),cout); }\
  108. \
  109. int int_type() const { return INT_TYPE(itype); }\
  110. \
  111. public:\
  112. \
  113. virtual etype& operator[](itype y)\
  114. { d_array_item i=(d_array_item)impl::lookup(Convert(y));\
  115.   if (i==nil) i=(d_array_item)impl::insert(Convert(y),Convert(this->init));\
  116.   return ACCESS(etype,impl::info(impl::item(i)));\
  117. }\
  118. \
  119. virtual bool defined(itype y) const\
  120. { return (impl::lookup(Convert(y))!=nil); }\
  121. \
  122. virtual void start_iteration() const\
  123. { (d_array_item&)iterator = (d_array_item)impl::first_item(); }\
  124. \
  125. virtual bool next_index(itype& y) const    \
  126. { if (iterator==0) return false;\
  127.   else\
  128.   {y = ACCESS(itype,impl::key(impl::item(iterator)));\
  129.    (d_array_item&)iterator=(d_array_item)impl::next_item(impl::item(iterator));\
  130.    return true;\
  131.   }\
  132. }\
  133. \
  134. _d_array_(itype,etype,impl)& operator=(const _d_array_(itype,etype,impl)& A)\
  135. { impl::operator=(A); this->init=A.init; return *this; }\
  136. \
  137. _d_array_class_(itype,etype,impl)()        { Init(this->init); }\
  138. _d_array_class_(itype,etype,impl)(etype i) { this->init=i; }\
  139. \
  140. _d_array_class_(itype,etype,impl)(const _d_array_(itype,etype,impl)& A) : impl(A)\
  141. { this->init=A.init; }\
  142. \
  143. virtual ~_d_array_class_(itype,etype,impl)() { impl::clear(); }
  144.  
  145. #if defined(__TEMPLATE_ARGS_AS_BASE__)
  146. #define _d_array_class_(a,b,c) _d_array
  147. #define _d_array_(a,b,c) _d_array<a,b,c>
  148. template <class itype, class etype, class impl> 
  149. _d_array_class(itype,etype,impl)
  150. };
  151. #else
  152. #define _d_array(a,b,c)         name4(a,b,c,_d_array)
  153. #define _d_array_class_(a,b,c)  name4(a,b,c,_d_array)
  154. #define _d_array_(a,b,c)        name4(a,b,c,_d_array)
  155. #define _d_arraydeclare3(_a,_b,_c) _d_array_class(_a,_b,_c) };
  156. #endif
  157.  
  158. #endif
  159.